package pl.klangner.recobox.geometry.algorithms
{
	import pl.klangner.recobox.geometry.LineSegment;
	
	/**
	 * Polyline simplification implemented using Douglas-Peucker Algorithm
	 * source: http://geometryalgorithms.com/Archive/algorithm_0205/algorithm_0205.htm
	 */
	public class DPPolylineSimplification
	{
	  // --------------------------------------------------------------------------------------------
		public function DPPolylineSimplification(){
			
			tolerance = 10;
		}

	  // --------------------------------------------------------------------------------------------
	  public function set tolerance(e:Number):void{
	  	_tolerance = e;
	  	_tolerance2 = e*e;
	  }	
		
	  // --------------------------------------------------------------------------------------------
	  /**
	  * Simplify polyline using Douglas-Peucker Algorithm
	  * source: http://geometryalgorithms.com/Archive/algorithm_0205/algorithm_0205.htm
	  * 
	  * @param points array of points which defines input polyline
	  * 
	  * @return array of points which defines simplified polyline
	  */
		public function simplify(points:Array):Array{
			var outputPoints : Array = new Array();			// simplified polyline
			var last : int = points.length-1;
			
			_polyline = points;
			_marked = new Array(points.length);
			_marked[0] = true;
			_marked[last] = true;
			
			// Reduce polyline
			reduce(0,last);
			
			// Copy vertices to new polyline
			for(var i:int=0; i<=last; i++){ 
				if(_marked[i]) {
					outputPoints.push(points[i]);
				}
			}
			
			return outputPoints;
			
		}
 
		// --------------------------------------------------------------------------------------------
		/** Reduce number of vertices */
		private function reduce(begin:int, end:int):void {

			if(end <= begin+1)
			 return;
			
			var maxi : int = begin;
			var maxd2 : Number = 0;
			var dv2 : Number;
			var ls:LineSegment = new LineSegment(_polyline[begin], _polyline[end]);

			for(var i:int=begin+1; i<end; i++) {
				
				dv2 = ls.distanceToSegment2(_polyline[i]);
				 if (dv2 > maxd2){
			        maxi = i;
  				    maxd2 = dv2;
   				 } 
			}
			
			
			if(maxd2 > _tolerance2) {
				_marked[maxi] = true;
				reduce(begin, maxi);
				reduce(maxi,end);
			}
		}
		

		// --------------------------------------------------------------------------------------------
		// Private members
		private var _tolerance:Number;
		private var _tolerance2:Number;
		private var _polyline:Array;					// Array with points of input polyline
		private	var _marked : Array; 					// Array with marked points
				
	}
}